PPA (complexidade) - definition. What is PPA (complexidade)
Diclib.com
قاموس ChatGPT
أدخل كلمة أو عبارة بأي لغة 👆
اللغة:

ترجمة وتحليل الكلمات عن طريق الذكاء الاصطناعي ChatGPT

في هذه الصفحة يمكنك الحصول على تحليل مفصل لكلمة أو عبارة باستخدام أفضل تقنيات الذكاء الاصطناعي المتوفرة اليوم:

  • كيف يتم استخدام الكلمة في اللغة
  • تردد الكلمة
  • ما إذا كانت الكلمة تستخدم في كثير من الأحيان في اللغة المنطوقة أو المكتوبة
  • خيارات الترجمة إلى الروسية أو الإسبانية، على التوالي
  • أمثلة على استخدام الكلمة (عدة عبارات مع الترجمة)
  • أصل الكلمة

%ما هو (من)٪ 1 - تعريف


PPA (complexidade)         
PPA é uma classe de complexidade, significando em inglês "Polynomial Parity Argument" (). Introduzido por Christos Papadimitriou em 1994 (página 528), PPA é uma subclasse de TFNP.
Complexidade ciclomática         
Complexidade ciclomática (ou complexidade condicional) é uma métrica de software usada para indicar a complexidade de um programa de computador. Desenvolvida por Thomas J.
Complexidade fatorial         
Representada por O(n!), é normalmente encontrada ao analisar a complexidade de algoritmos de força bruta, que tentam todas as possibilidades para problemas de otimização combinatória.

ويكيبيديا

PPA (complexidade)

PPA é uma classe de complexidade, significando em inglês "Polynomial Parity Argument" (em português: Argumento de Paridade Polinomial). Introduzido por Christos Papadimitriou em 1994 (página 528), PPA é uma subclasse de TFNP. É uma classe de problemas de busca que podem ser demonstrados como totais através de uma aplicação do lema do aperto de mão: qualquer grafo não-direcionado que possui um vértice cujo grau é um número ímpar deve ter outro vértice cujo grau é um número ímpar. Essa observação implica que dado um grafo e um vértice de grau ímpar, e for pedido para encontrarmos outro vértice de grau ímpar, então estamos procurando por algo cuja existência é garantida (então, temos um problema de busca total).

PPA é definida do seguinte modo. Suponha que temos um grafo cujos vértices são strings binárias de  n {\displaystyle n}  bits, e o grafo é representado por um circuito de tamanho polinomial que recebe um vértice como entrada e produz como saída os seus vizinhos. (Note que isso nos permite representar um grafo de tamanho exponencial sobre o qual podemos realizar exploração local com eficiência). Suponha também que um vértice específico (digamos o vetor composto apenas por zeros) possui um número ímpar de vizinhos. É necessário encontrar outro vértice de grau ímpar. Note que esse problema está em NP—dado uma solução, a sua corretude pode ser verificada através do circuito. Um problema de computação de funão pertence a PPA se ele admitir uma redução em tempo polinomial a esse problema de busca em grafo. Um problema é completo para a classe PPA se além disso, esse problema de busca em grafo for reduzível a esse problema.

PPA contém PPAD como subclasse. Isso é porque o problema correspondente que define PPAD, conhecido como FIM DA LINHA, pode ser reduzido (de uma maneira simples) para o problema de busca acima para um vértice de grau ímpar adicionar (essencialmente, apenas ignorando as direções das arestas em FIM DA LINHA).

Há uma versão não-orientada do lema de Sperner conhecidamente completo para PPA. O problema de busca para um segundo Ciclo Hamiltoniano em um grafo 3-regular é um membro de PPA, mas não se sabe se é completo para PPA.